package com.mystudy.leetcode.problem.link.p_86;

import com.mystudy.leetcode.base.ListNode;
import com.mystudy.leetcode.base.ListNodeUtils;
import org.junit.Test;

/**
 * @author 周志龙
 * @Email 15216876513@163.com
 * @Date on 2019/7/9 21:47
 * @Description 中等问题：分隔列表
 */
public class Solution {


    @Test
    public void test() {
        ListNode listNode = ListNodeUtils.generateLinkList(new int[]{1, 4, 3, 2, 5, 2});
        ListNode partition = partition(listNode, 3);
        ListNodeUtils.show(partition);
    }


    public ListNode partition(ListNode head, int x) {
        ListNode minDummyHead = new ListNode(-1);
        ListNode maxDummyHead = new ListNode(-1);

        ListNode cur = head;
        ListNode minCur = minDummyHead;
        ListNode maxCur = maxDummyHead;
        while (cur != null) {
            if (cur.val >= x) {
                maxCur.next = cur;
                maxCur = cur;
            } else {
                minCur.next = cur;
                minCur = cur;
            }
            cur = cur.next;
        }
        maxCur.next = null;

        minCur.next = maxDummyHead.next;

        return minDummyHead.next;


    }
}
